A data structure is suggested for efficient implementation of operations such as Search, Insert, Delete, Min, Next, Scan. The idea (proposed independently by Franklin and by Melville and Gries) is to maintain an ordered list of the elements (keys) in which an element may appear more than once. Insertion, as a typical operation, is done by (binary) search followed by some move operations. We show that the expected number of move operations is bounded (in the size of the table), provided that the density of dummy keys in the table is bounded away from 1. The probabilistic model assumes that all permutations of the input are equiprobable. As a result of the analysis, a flaw in both Franklin's and Melville and GrIes' analyses was found. To improve the worst case behavior, a variant of the sparse table scheme is suggested. In that version, a sequence of n insertions into a table ef size n may not take more than O(n (log n)2)
By: Alon Itai, Alan G. Konheim, Michael Rodeh
Published in: RC8550 in 1980
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .